Polygonal surfaces are widely used for representing three dimensional (3-D) geometric models. Such surfaces consist of a plurality of polygons, which are cycles of vertices, whose coordinates are generally expressed in a modeling space coordinate system. The polygonal surfaces may be used for generating pictures and animations, and may also be used in Computer Aided Design (CAD) systems, in scientific visualization, and in medical imaging.
Although modeling systems used in Mechanical Computer Aided Design and in animation are expanding their geometric domain to include free form surfaces, polygonal models remain the primary 3D representation used in the manufacturing, architectural, Geographic Information Systems, geoscience, and entertainment industries. Polygonal models are particularly effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mock-up applications involving complex CAD models.
Since methods are known in the prior art for easily and efficiently triangulating arbitrary polygonal faces, it is sufficient to consider geometric models which are defined by triangular meshes. For example, a method to triangulate the faces of a polygonal model is described by Ronfard, R. and Rossignac, J. in "Triangulating multiply-connected polygons: A simple, yet efficient algorithm", Computer Graphics Forum, V. 13, No. 3, 1994, pp. 281-292.
A "triangular mesh" is defined by the position of its vertices ("geometry"), which are N-dimensional vectors, by the association between each triangle and its sustaining vertices ("connectivity"), and by colors, normals, and texture coordinates ("properties"), which do not affect the geometry, but influence the way it is shaded.
A triangular mesh with V vertices and T triangles is typically represented in the prior art (for example, as described by Foley et.al. in "Computer Graphics: Principles and Practice", Addison-Wesley, 1990) by a "vertex positions array", a "triangle array", and (optionally) one or more "property arrays". The position of each vertex of the triangular mesh is represented in the vertex positions array by N floating point coordinates. Each triangle of the triangular mesh is represented in the triangle array by three indices to the vertex positions array.
A triangular mesh may also have continuous or discrete properties, such as colors, normals, and texture coordinates, associated with its vertices or triangles. To model various discontinuous phenomena on the triangular mesh, properties can also be associated with each vertex of each triangle. These (triangle,vertex) pairs are called "corners", and the corresponding properties "corner" properties. These corner properties are represented in the optional property arrays.
Triangular meshes are typically classified (for example, as described by Hoffmann, C., "Geometric and Solid Modeling", Morgan Kaufmann, 1989) as manifolds and non-manifolds. An "edge" of a triangular mesh is a pair of vertices in a triangle, without taking into account the order of the two vertices within the edge. The two vertices of an edge are called endpoints of the edge. The triangle is said to be incident to the edge, and the edge incident to the vertices. Two triangles sharing an edge are said to be adjacent. Two edges sharing a vertex are said to be adjacent. The set of triangles that share a vertex are referred to as the star of the vertex. The number of triangles in the star of a vertex can be referred to as the valence of the vertex. The link of a vertex is obtained by connecting all adjacent edges bounding the star of the vertex and discarding from the list of edges so formed the edges incident to the vertex. If the link has one component, and is not intersecting itself, the vertex is said to be a regular vertex, otherwise it is referred to-as a singular vertex. For a regular vertex, if the link is closed, meaning that the first end point of the first edge of the link is the same as the last end point of the last edge, the vertex is an interior regular vertex, otherwise it is a boundary vertex.
The edges of a triangular mesh define a partition of the vertices of the triangular mesh into one or more disjoint subsets of vertices such that the two endpoints of each edge of the triangular mesh belong to the same subset. This partition of the vertices of the triangular mesh defines an associated partition of the triangles of the triangular mesh into one or more disjoint subsets of triangles, which are in one to one correspondence with the subsets of vertices. The subset of triangles associated with a subset of vertices is composed of all the triangles of the triangular mesh with vertices in the subset of vertices. If the triangular mesh has properties, the partition of the vertices also defines corresponding partitions of the properties in a similar manner. Each subset of vertices, the corresponding subset of triangles, and (optionally) the corresponding subsets of properties define a new triangular mesh which is called a "connected component" of the triangular mesh.
A triangular mesh is referred to as a "manifold triangular mesh" if the following two conditions are satisfied: 1) if any two triangles of the triangular mesh intersect, the intersection is either a common vertex or a common edge; and 2) all the vertices of the triangular mesh are regular vertices, which implies that each edge of the triangular mesh is shared by at most two triangles.
An edge of a manifold triangular mesh may have either one or two incident triangles. An "interior edge" is an edge with two incident triangles. A "boundary edge" is an edge with one incident triangle. It is known that the endpoints of the boundary edges of a manifold triangular mesh are boundary vertices, and that the boundary vertices of a manifold triangular mesh are endpoints of the boundary edges. The boundary edges of a manifold triangular mesh can be partitioned into one or more disjoint subsets of boundary edges referred to as "boundaries", such that two boundary edges which share a boundary vertex as a common endpoint belong to the same boundary. It is also known that each boundary vertex of a manifold triangular mesh is the endpoint of exactly two boundary edges.
It has been found that typical polygonal surfaces may be so large that real time interaction is impossible using currently available hardware, or that the transmission of the data describing the surfaces over computer networks is unacceptably slow. Providing different resolutions, or levels of details (LODs), of such polygonal surfaces overcomes this problem, as it is possible to use an appropriate lower LOD for a given task. Such LODs may be generated using a software modeling tool or by using algorithms that automatically produce LODs. One example of such algorithms is described in commonly assigned U.S. Pat. No. 5,448,686 "Multi-Resolution Graphic Representation Employing at Least One Simplified Model for Interactive Visualization Applications", by P. Borrel and J. Rossignac, the disclosure of which is incorporated by reference herein in its entirety. Another example of a LOD generation algorithm is described in commonly assigned U.S. Patent Application "Surface Simplification Preserving a Solid Volume and Respecting Distance Tolerances", Ser. No. 08/742,631 filed Nov. 1, 1996, by A. Gueziec, herein incorporated by reference in its entirety. Reference in this regard may also be had to a publication entitled "Surface Simplification with Variable Tolerance", A. Gueziec, Second Annual International Symposium on Medical Robotics and Computer Assisted Surgery, pages 132-139, Baltimore, Md., November 1995.
Such polygonal surfaces and LODs of polygonal surfaces are increasingly exchanged over computer networks. When transmitting several LODs of the same polygonal surface, it is desirable to avoid transmitting duplicate information.
In addition, when transmitting the data through a computer network, one may wish to progressively display a surface such that while the computer is busy preparing high resolution images, lower resolution images are quickly available for display and interaction using simplified models.
Conventional methods for producing levels of details from polygonal surfaces include four techniques, described by Hoppe "Progressive Meshes", Proceedings of ACM SIGGRAPH'93, pp.99-108, by Eck et al. "Multi-resolution analysis of arbitrary meshes", Proceedings of ACM SIGGRAPH'95, pp. 173-182, by Popovic et al. "Progressive Simplicial Complexes", Proceedings of ACM SIGGRAPH'97, pp. 217-224, and by De Floriani et al. "Building and Traversing a Surface at Variable Resolution", IEEE Visualization'97, pp. 103-110. The technique of Hoppe builds a progressive mesh representation that consists of a description of the transition from a simplified mesh to the original mesh. Hoppe sends a succession of "vertex splits", in order to undo the edge collapses that he performed earlier. For each of these vertex splits, he must specify the indices in the original mesh of the simplified vertex resulting from the collapse, as well as the indices of the neighboring vertices where the new triangles will be inserted. In addition, the displacement of the new vertex with respect to the previous position of the vertex must be specified.
One problem with Hoppe's Progressive Meshes technique is that each vertex split information contains a vertex identification (ID), the position of two vertices after splitting, and the relative position of two vertices in the neighborhood of the first vertex. This results in sending a significant amount of information. Since the number of vertex splits that are specified are generally on the order of magnitude of n, the information that must be provided with Hoppe's method can be assumed to be on the order of n*log(n) or higher.
Another drawback to the use of Hoppe's method is that each individual vertex split must be specified.
The technique of Eck et al. builds an approximation of the original mesh that has the same connectivity as a subdivided surface. The position of the vertices are treated as a signal decomposed over a multi-resolution wavelet basis. Levels of detail are obtained by varying the number of wavelet coefficients that are transmitted. One problem with this approach is that the highest level of detail is still an approximation to the original polyhedron, and one may need to provide an unacceptably large number of wavelet coefficients to approach the original polygonal surface with sufficient accuracy. In general, this technique is only suitable if a lossy result for geometry and topology is acceptable. It should also be noted that Eck's techniques for building the base surface are complex and computationally expensive. Further, it should be noted that when the topology of the surface is fairly complex, i.e, when the surface has a large number of boundary curves or an Euler characteristic largely higher or largely lower than zero (for instance, a torus has an Euler characteristic of 0, a double torus of -2, a triple torus of -4 and so on, a disk has one boundary curve corresponding to the outer circle of the disk; boundary curves and the Euler characteristic are defined in various textbooks such as Massey's "Algebraic Topology", Springer Verlag, 1977), it is not clear whether Eck's method and related methods can obtain a useful approximation of the surface.
The Progressive Simplicial Complexes technique of Popovic and Hoppe is a generalization of the Progressive Meshes technique to simplicial complexes formed with points, lines, surfaces and volumes. A vertex split is replaced with a "generalized vertex split", and additional information is necessary to encode whether the added vertex will add a point, a line segment, a triangle, or a tetrahedron to the complex. This method suffers from the same limitations as Hoppe's, when applied to a polygonal surface.
The Multi-Triangulation technique of De Floriani et al. is essentially a method for representing several levels of detail of a surface simultaneously, using a directed acyclic graph whose nodes represent increases and decreases of the number of triangles and whose arcs represent the dependencies between such increases or decreases. It is not stated how the levels of detail could be transmitted efficiently.